package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:41
 * @Des 链表型数两数相加
 */
public class LeetCode_445 {
    public static void main(String[] args) {
        /**
         * 数据准备
         */
        LinkNode num1 = new LinkNode(6);
        int[] vals = {};
        num1 = LinkNode.formLink(num1,vals);

        LinkNode num2 = new LinkNode(8);
        int[] vals1 = {};
        num2 = LinkNode.formLink(num2,vals1);

        List<Integer> num1List = new ArrayList<>();
        List<Integer> num2List = new ArrayList<>();

        LinkNode numTemp = num1;
        while (numTemp != null) {
            num1List.add(numTemp.val);
            numTemp = numTemp.next;
        }

        numTemp = num2;
        while (numTemp != null) {
            num2List.add(numTemp.val);
            numTemp = numTemp.next;
        }

        int max1 = num1List.size() - 1;
        int max2 = num2List.size() - 1;
        List<Integer> sum = new ArrayList<>();
        int carry = 0;
        for( ; max1 >= 0 || max2 >= 0 ; max1--,max2--) {
            int bit1 = max1 < 0 ? 0 : num1List.get(max1);
            int bit2 = max2 < 0 ? 0 : num2List.get(max2);

            int bitSum = bit1 + bit2 + carry;
            sum.add(bitSum % 10);

            carry = bitSum > 9 ? 1 : 0;
        }
        if(carry == 1)
            sum.add(carry);

        LinkNode root = new LinkNode(0);
        LinkNode sumLink= new LinkNode();
        root.next = sumLink;
        for (int i = sum.size() - 1;i >= 0;i--) {
            sumLink.val = sum.get(i);

            if(i == 0) {
                sumLink.next = null;
                break;
            }
            sumLink.next = new LinkNode();
            sumLink = sumLink.next;
        }
        LinkNode.headToString(root.next);
    }
}
